
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Enumeration;
import java.util.Observable;
import java.util.Observer;
import java.util.Random;

public class Formiga extends Observable implements Runnable{
	
	private int numFormiga; //ID da formiga
	
	private static final double B    = 2;
	private static final double Q0   = 0.8;
	private static final double R    = 0.1;
	
	private static PrintStream print;
	
	protected ArrayList<Cidade> melhorRota;
    protected Cidade   cidadeAtual; //Cidade atual
    protected Cidade   cidadeInicio; //Cidade de Início da rota
    protected double   valorMelhorRota; //Valor da distância total da melhor rota encontrada
    protected Observer observer; 
    protected ArrayList<Cidade> cidadesParaVisitar;
    
    private static int numeroFormigas; //Número total de formigas
    
    private static final Random aleatorio = new Random(System.currentTimeMillis());
    
    protected static Colonia colonia; //Colônia a que pertence
    
    public static double VALOR_MELHOR_ROTA_GLOBAL = Double.MAX_VALUE; //Valor da distância da malhor rota global encontrada
    public static ArrayList<Cidade> MELHOR_ROTA_GLOBAL = null; //ArrayList ordenada da melhor rota encontrada
    public static int NUMERO_MELHOR_ITERACAO = 0;
    
    
    public Formiga(Cidade pCidadeInicio, Observer pObserver) { //Construtor de uma formiga
    	
		numeroFormigas++;
		numFormiga = numeroFormigas;
		cidadeInicio = pCidadeInicio;
		observer = pObserver;

	}
    
    public void init()
    {
    	
    	if(print == null)
        {
            try
            {
            	print = new PrintStream(new FileOutputStream("/home/david/testes/" + colonia.getGrafo().getP().getNome() +"_" + colonia.getNumColonia() +"_" +  colonia.getGrafo().getNumCidades() + "x" + colonia.getFormigas().size() + "x" + colonia.getNumeroIteracoes() + "_ants.txt"));
            }
            catch(Exception ex)
            {
                ex.printStackTrace();
            }
        }

        final Grafo grafo = colonia.getGrafo();
        cidadeAtual = cidadeInicio;
        melhorRota  = new ArrayList<Cidade>();
        
        melhorRota.add(cidadeInicio);
        valorMelhorRota = 0;
        
        cidadesParaVisitar = (ArrayList<Cidade>)grafo.getCidades().clone(); //Cidades para visitar, todas
        cidadesParaVisitar.remove(cidadeInicio); //Remove a cidade de inicio

    }
    
    public void start()
    {
        init();
        Thread thread = new Thread(this);
        thread.setName("Formiga " + numFormiga);
        thread.start();
    }
    
    public void run()
    {
        final Grafo grafo = colonia.getGrafo();
        
        
        while(!fim()){
            Cidade novaCidade;
            
            // Grafo tem que ser sincronizado
            synchronized(grafo)
            {
                //Decide qual a próxima cidade a visitar
                novaCidade = equacaoDeTransicao(cidadeAtual);
                
               //Soma a distância da nova cidade visitada
                valorMelhorRota += grafo.getDistancia(cidadeAtual.getNum(), novaCidade.getNum());
            }
                        
            // Adiciona a cidade visitada à lista de cidades
            melhorRota.add(novaCidade);
  
                        
            synchronized(grafo)
            {
              
                equacaoAtualizacaoFeromoneo(cidadeAtual, novaCidade);
            }
            
    
            cidadeAtual = novaCidade;
        }
        
        synchronized(grafo)
        {
            if(melhor(valorMelhorRota, VALOR_MELHOR_ROTA_GLOBAL))
            {
                VALOR_MELHOR_ROTA_GLOBAL        = valorMelhorRota;
                MELHOR_ROTA_GLOBAL              = melhorRota;
                NUMERO_MELHOR_ITERACAO = colonia.getContadorIteracao();
                print.println("F: " + numFormiga + ": " + valorMelhorRota + ", " + colonia.getContadorIteracao());

            }
        }
        
        
        //Atualiza o observer
        observer.update(this, null);
      
        if(colonia.fim()){

            print.close();
        }
    }
        
    public synchronized Cidade equacaoDeTransicao(Cidade cidadeAtual)  {
            final Grafo grafo = colonia.getGrafo();
            
            double q    = aleatorio.nextDouble();
            Cidade melhorCidade = null;
            
            if(q <= Q0) 
            {

                double valorMaximo = -1;
                double valor;
                int numCidade;
                Enumeration<Cidade> cds = Collections.enumeration(cidadesParaVisitar);
                
                while(cds.hasMoreElements())
                {
                	
                	numCidade = (cds.nextElement()).getNum();
                	
                    
                    // Checa atração
                    if(grafo.getAtracao(cidadeAtual.getNum(), numCidade) == 0)
                        throw new RuntimeException("Atração = 0");
                    
                    //Atração mais visibilidade
                    valor = grafo.getAtracao(cidadeAtual.getNum(),numCidade) * Math.pow(grafo.getVisibilidade(cidadeAtual.getNum(),numCidade), B);
                    
                    // Checa se é o melho valor.
                    if(valor > valorMaximo)
                    {
                        valorMaximo  = valor;
                        
                        melhorCidade = grafo.getCidades().get(numCidade);
                    }
                }
            }
            else  // Exploração
            {
                double soma = 0;
                int numCidade = -1;
                Enumeration<Cidade> cds = Collections.enumeration(cidadesParaVisitar);
                
                while(cds.hasMoreElements())
                {
                	
                	numCidade = (cds.nextElement()).getNum();
                	
                    
                    if(grafo.getAtracao(cidadeAtual.getNum(), numCidade) == 0)
                        throw new RuntimeException("Atração = 0");
                    
                    // Atualiza a soma
                    soma += grafo.getAtracao(cidadeAtual.getNum(), numCidade) * Math.pow(grafo.getVisibilidade(cidadeAtual.getNum(),numCidade), B);
                }
                
                if(soma == 0)
                    throw new RuntimeException("Soma = 0");
                
                // Pega a média
                double media = soma / (double)cidadesParaVisitar.size();
                
                // search the node in agreement with eq. b)
                while(!cidadesParaVisitar.isEmpty() && melhorCidade != null)
                {
                	int i = 0;
                	numCidade = cidadesParaVisitar.get(i).getNum();
                    
                    double p =
                        (grafo.getAtracao(cidadeAtual.getNum(), numCidade) * Math.pow(grafo.getVisibilidade(cidadeAtual.getNum(), numCidade), B)) / soma;
                    
                    // Se p é maior que a média a Cidade é boa 
                    if((grafo.getAtracao(cidadeAtual.getNum(), numCidade) *	Math.pow(grafo.getVisibilidade(cidadeAtual.getNum(),
                    		numCidade), B)) > media)                    {
                        //System.out.println("Found");
                    	 melhorCidade = grafo.getCidades().get(numCidade);
                    }
                    i++;
                }
                
                if(melhorCidade == null)
                	 melhorCidade = grafo.getCidades().get(numCidade);
           }
                     
            if(melhorCidade == null)
                throw new RuntimeException("melhorCidade = null");
            
            cidadesParaVisitar.remove(melhorCidade);
            
            return melhorCidade;
        }
        
    public synchronized void equacaoAtualizacaoFeromoneo(Cidade cidadeAtual, Cidade proximaCidade)
        {
            final Grafo grafo = colonia.getGrafo();
            
            // Intensidade do feromoneo
            double val =
                ((double)1 - R) * grafo.getAtracao(cidadeAtual.getNum(), proximaCidade.getNum()) +
                (R * (grafo.atracaoTempoZero()));
            
            // Atualiza atração
            grafo.atualizaAtracao(cidadeAtual.getNum(), proximaCidade.getNum(), val);
        } 
    
	public static Colonia getColonia() {
		return colonia;
	}
	public static void setColonia(Colonia colonia) {
		Formiga.colonia = colonia;
	}
	
    public static void reseta()
    {
    	VALOR_MELHOR_ROTA_GLOBAL = Double.MAX_VALUE;
    	MELHOR_ROTA_GLOBAL = null;
    	NUMERO_MELHOR_ITERACAO = 0;
    }
    
    public boolean melhor(double valorRota1, double valorRota2)
    {
        return valorRota1 < valorRota2;
    }
    public String toString()
    {
        return "Formiga " + numFormiga;
    }
    
    public boolean fim()
    {
        return cidadesParaVisitar.isEmpty();
    }

	public static String getStringMELHOR_ROTA_GLOBAL() {
		String rota = "";
		for(Cidade c:MELHOR_ROTA_GLOBAL){
			rota += c.getNum()+" ";
		}
		return rota;
	}

	public static void setMELHOR_ROTA_GLOBAL(ArrayList<Cidade> mELHORROTAGLOBAL) {
		MELHOR_ROTA_GLOBAL = mELHORROTAGLOBAL;
	}

    
}
